Minimum Cost Up the Stair

Problem

This is a problem modified from the number of ways up the stair problem, instead of being a counting problem, it is now a minimization problem.

Problem Description

You are given an integer array $\text{cost}$ where $\text{cost}[i]$ is the cost of $i$-th step on a staircase. Once you pay the cost, you can either climb $1$ or $2$ steps.

You can either start from the step with index $0$, or the step with index $1$.

Find the minimum cost to reach the top of the stair.

Given:

• 0 < cost.length

Testcases

Input: cost = [10,15,20]
Output: 15

The optimal path:

1. Start at index 1.
2. Pay 15 to climb one step to reach the top.

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6

The optimal path:

1. Start at index 0.
2. Pay 1 to climb two steps to reach index 2.
3. Pay 1 to climb two steps to reach index 4.
4. Pay 1 to climb two steps to reach index 6.
5. Pay 1 to climb one step to reach index 7.
6. Pay 1 to climb two steps to reach index 9.
7. Pay 1 to climb one step to reach the top.

---

Solution

Subproblems

At the $n$-th step, instead of focusing on the number of ways to reach the $n$-th step, we focus on the cost to reach the $n$-th step:

1. With a cost of $\text{cost}[n-1]$, take $1$ step from the $(n-1)$-th step.
2. With a cost of $\text{cost}[n-2]$, take $2$ steps from the $(n-2)$-th step.

We see the subproblems is almost the same as the original problem, the only difference is the cost of taking the steps.

Recurrence Relation

Since we want to minimize the cost, we want to take which ever costs less. In other words, we want to take the minimum of the two costs.

Let $f(n)$ be the minimum cost to reach the $n$-th step:

$$f(n) = \min \begin{cases} f(n-1) + \text{cost}[n-1] \\ f(n-2) + \text{cost}[n-2] \end{cases}$$

Multiple Lines to Express Cases

Instead of writing the relation in one line like in the previous chapters (e.g. $f(n) = f(n-1) + f(n-2)$), we will write it in multiple lines to make it clearer the number of subproblems in the relation in future chapters.

Base Cases

As for the base cases, since we can start at index $0$ or $1$, both of their costs are $0$.

$$\begin{aligned} f(0) &= 0 \\ f(1) &= 0 \end{aligned}$$

Solving the Problem

We can solve the problem using the same approach as the number of ways up the stair problem, the only difference is to use $\min$ instead of $+$ in the recurrence relation.

In addition, the base cases can all be initialized to $0$ instead of specific values.

Minimum Cost Up the Stair

function min_cost_up_the_stair(cost: int[]) -> int {
    // the problem size
    let n = cost.length

    // initialize memoization array
    let dp = [...] of size n + 1
             zero-based index
             initialized to 0

    // calculate next values
    for i from 2 to n {
        dp[i] = min(
            dp[i - 1] + cost[i - 1],
            dp[i - 2] + cost[i - 2],
        )
    }

    return dp[n]
}

Time complexity: $O(n)$
Space complexity: $O(n)$

The solution to the minimum cost up the stair problem with $\text{cost} = [1,5,2,4,3]$.

Try it out

$\text{cost} = [$

$]$

cost	1	5	2	4	3
dp	0	0	1	3	3	6
cost + dp	1	5	3	7	6

Green bold values forms the path of the minimum cost to reach that step.

Space Optimization

Since the subproblems is the same as the number of ways up the stair problem, we can optimize the space complexity to $O(1)$ in the same way, only storing the previous two values.

Minimum Cost Up the Stair - Space Optimized

function min_cost_up_the_stair(cost: int[]) -> int {
    // the problem size
    let n = cost.length

    // initialize base cases
    let prev = 0
    let curr = 0

    // calculate next values
    for i from 2 to n {
        let next = min(
            curr + cost[i - 1],
            prev + cost[i - 2],
        )
        prev = curr
        curr = next
    }

    return curr
}

Time complexity: $O(n)$
Space complexity: $O(1)$

The space optimized solution to the minimum cost up the stair problem with $\text{cost} = [1,5,2,4,3]$.

Checkpoint

In this problem, what do we take from the subproblems to get the larger problem from the subproblems?

The summation of the costs

The minimum of the costs

The summation of the combination to reach the step

The number of subproblems

Implementation

Python

Minimum Cost Up the Stair

def minCostUpTheStair(cost):
    # the problem size
    n = len(cost)

    # initialize memoization array
    dp = [0] * (n + 1)

    # calculate next values
    for i in range(2, n + 1):
        dp[i] = min(
            dp[i - 1] + cost[i - 1],
            dp[i - 2] + cost[i - 2],
        )

    return dp[n]

Minimum Cost Up the Stair - Space Optimized

def minCostUpTheStair(cost):
    # the problem size
    n = len(cost)

    # initialize base cases
    prev = 0
    curr = 0

    # calculate next values
    for i in range(2, n + 1):
        next = min(
            curr + cost[i - 1],
            prev + cost[i - 2],
        )
        prev = curr
        curr = next

    return curr

C++

Note that we do not need to check for index out of bound error like the implementation for the number of ways up the stair problem, since we can initialize the memoization vector with values of 0 all together.

Minimum Cost Up the Stair

#include <vector>
#include <algorithm>

int min_cost_up_the_stair(std::vector<int>& cost) {
    // the problem size
    int n = cost.size();

    // initialize memoization vector
    std::vector<int> dp(n + 1, 0);

    // calculate next values
    for (int i = 2; i <= n; i++) {
        dp[i] = std::min(
            dp[i - 1] + cost[i - 1],
            dp[i - 2] + cost[i - 2]
        );
    }

    return dp[n];
}

Minimum Cost Up the Stair - Space Optimized

#include <vector>
#include <algorithm>

int min_cost_up_the_stair(std::vector<int>& cost) {
    // the problem size
    int n = cost.size();

    // initialize base cases
    int prev = 0;
    int curr = 0;

    // calculate next values
    for (int i = 2; i <= n; i++) {
        int next = std::min(
            curr + cost[i - 1],
            prev + cost[i - 2]
        );
        prev = curr;
        curr = next;
    }

    return curr;
}

Rust

Minimum Cost Up the Stair

fn min_cost_up_the_stair(cost: Vec<i32>) -> i32 {
    // the problem size
    let n = cost.len();

    // initialize memoization vector
    let mut dp = vec![0; n + 1];

    // calculate next values
    for i in 2..=n {
        dp[i] = std::cmp::min(
            dp[i - 1] + cost[i - 1],
            dp[i - 2] + cost[i - 2],
        );
    }

    dp[n]
}

Minimum Cost Up the Stair - Space Optimized

fn min_cost_up_the_stair(cost: Vec<i32>) -> i32 {
    // the problem size
    let n = cost.len();

    // initialize base cases
    let mut prev = 0;
    let mut curr = 0;

    // calculate next values
    for i in 2..=n {
        let next = std::cmp::min(
            curr + cost[i - 1],
            prev + cost[i - 2],
        );
        prev = curr;
        curr = next;
    }

    curr
}

---

Related Topics

LeetCode - Min Cost Climbing Stairs: https://leetcode.com/problems/min-cost-climbing-stairs/